package leetcode.code1763;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：3 ms, 在所有 Java 提交中击败了83.33%的用户
//
//内存消耗：41.4 MB, 在所有 Java 提交中击败了5.26%的用户
//
//通过测试用例：73 / 73
public class Solution implements IDebug {

	public String longestNiceSubstring(String s) {
		int len = s.length();
		char[] cs = s.toCharArray();
		int max = 0, maxL = -1, maxR = 0;
		int M = 0, m = 0, N = 0, n = 0;
		int move = 1;
		int[] B = new int[26];
		int[] b = new int[26];
		int[] C = new int[26];
		int[] c = new int[26];
		for (int i = 0; i < len; i++) {
			char in = cs[i];
			if (in >= 'a' && in <= 'z') {
				move = in - 'a';
				m |= 1 << (move);
				b[move]++;
			} else {
				move = in - 'A';
				M |= 1 << (in - 'A');
				B[move]++;
			}
			N = M;
			n = m;
			C = Arrays.copyOf(B, B.length);
			c = Arrays.copyOf(b, b.length);
			for (int j = 0; j < i; j++) {
				if (n == N && i - j > max) {
					max = i - j;
					maxL = j;
					maxR = i;
				}
				char out = cs[j];
				if (out >= 'a' && out <= 'z') {
					move = out - 'a';
					c[move]--;
					if (c[move] == 0) {
						n -= (n & (1 << move));
					}
				} else {
					move = out - 'A';
					C[move]--;
					if (C[move] == 0) {
						N -= (N & (1 << move));
					}
				}
			}
		}
		return maxL == -1 ? "" : new String(cs, maxL, maxR - maxL + 1);
	}

	@Override
	public void debug1() {
		HelpDebug.compare("aAa", this.longestNiceSubstring("YazaAay"));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare("Bb", this.longestNiceSubstring("Bb"));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare("", this.longestNiceSubstring("c"));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare("dD", this.longestNiceSubstring("dDzeE"));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
